//
// Description: 347. 前 K 个高频元素
// Created by Loading on 2021/9/24.
//

#include <bits/stdc++.h>

using namespace std;

vector<int> topKFrequent(vector<int> &nums, int k) {
    vector<int> res;

    // 统计元素次数
    unordered_map<int, int> cnt;
    for (auto &x : nums) {
        cnt[x]++;
    }

    // 优先级队列，次数优先，pair<int, int> 储存次数和元素
    priority_queue<pair<int, int>, vector<pair<int, int>>> q;
    for (auto it : cnt) {
        q.emplace(pair<int, int>{it.second, it.first});
    }
    while (k--) {
        res.emplace_back(q.top().second);
        q.pop();
    }

    return res;
}

int main() {
    vector<int> nums = {1, 1, 1, 2, 2, 3};
    int k = 2;
    vector<int> res = topKFrequent(nums, k);
    for (auto &x : res) {
        cout << x << " ";
    }
    cout << endl;

    return 0;
}